/*
 * @lc app=leetcode.cn id=516 lang=javascript
 *
 * [516] 最长回文子序列
 */

// @lc code=start
/**
 * @param {string} s
 * @return {number}
 */
var longestPalindromeSubseq = function (s) {
  const n = s.length;
  // 字符串 s 从索引 i 到 j 的子序列中的最长回文子序列的长度。
  const maxSubLen = Array.from({ length: n }, () => new Array(n).fill(0));
  // 先确定状态转移方程，根据方程确定遍历区间，遍历顺序
  for (let j = 0; j < n; j++) {
    for (let i = j; i >= 0; i--) {
      if (i === j) {
        maxSubLen[i][j] = 1;
        continue;
      }
      if (s[i] === s[j]) maxSubLen[i][j] = maxSubLen[i + 1][j - 1] + 2;
      else maxSubLen[i][j] = Math.max(maxSubLen[i + 1][j], maxSubLen[i][j - 1]);
    }
  }
  return maxSubLen[0][n - 1];
};
// @lc code=end
